﻿#include "stdafx.h"
#include "MinStack.h"

using namespace std;

namespace algorithm {
    CMinStack::CMinStack()
    {
    }

    void CMinStack::push(int val)
    {
        if (m_stack.empty()) {
            // 栈为空时，初始化最小值为当前值
            m_minValue = val;
        }
        // 计算val与最小值的差值
        long long diff = (long long)val - m_minValue;
        if (diff < 0) {
            // 如果差值小于0，表示val比当前最小值更小，此时修改最小值
            m_minValue = val;
        }
        m_stack.push(diff);
    }

    void CMinStack::pop()
    {
        if (m_stack.empty()) {
            return;
        }
        // 取出差值
        long long diff = m_stack.top();
        if (diff < 0) {
            /*
             * 如果差值小于0，表示当时push该值时修改了最小值，修改的最小值为当时push的val
             * 即此时m_minValue=当时的val，而diff等于val-m_minValue(push前的最小值)，
             * 因此可以逆计算出 push前的最小值 = m_minValue(当时的val) - diff;
             */
            m_minValue = (int)(m_minValue - diff);
        }
        m_stack.pop();
    }

    int CMinStack::top()
    {
        if (m_stack.empty()) {
            return -1;
        }
        // 取出差值
        long long diff = m_stack.top();
        if (diff < 0) {
            /*
             * 如果差值小于0，表示当时push该值时修改了最小值，修改的最小值为当时push的val
             * 即此时m_minValue=当时的val
             */
            return m_minValue;
        }
        else {
            return (int)(m_minValue + diff);
        }

    }

    int CMinStack::getMin()
    {
        return m_minValue;
    }
}
